// 给定一个n*n大小的二维矩阵matrix，将二位矩阵matrix顺时针旋转90,说明，不使用额外的数组空间
// 思路1：寻找规律
// 矩阵中第i行，第j列的点，经过90度顺时针旋转后，出现在第j行，倒数第i列
// 一次遍历可以确定4个点的位置
/**
 * i，j
   j , n - i - 1
   n - i - 1, n - j - 1
   n -j - 1, i 
得从后往前推，因为是后面赋值给前面
[  [i, j],  [n -j - 1, i], [n-i-1, n-j- 1], [j, n-i-1]]  = [[n-j-1, i], [n-i-1, n-j- 1], [j, n-i-1], [i, j]]
 * 
 */
function rotate(matrix) {
    let n = matrix.length
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
            [matrix[i][j], matrix[n - 1 - j][i], matrix[n - 1 - i][n - 1 - j], matrix[j][n - 1 - i]] = [matrix[n - 1 - j][i], matrix[n - 1 - i][n - 1 - j], matrix[j][n - 1 - i], matrix[i][j]];
        }
    }
    return matrix
}

// 时间复杂度为On^2
// 空间复杂度为O1

let matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
let matrix2 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate(matrix1)
console.log(matrix1);

rotate(matrix2)
console.log(matrix2);

// 思路2，原地翻转，原矩阵可以通过一次水平翻转 + 主对角线（第一行第一列到最后一行最后一列的对角线）翻转，得到旋转后的二维矩阵

function rotate2(matrix) {
    let n = matrix.length

    // 水平翻转
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < n; j++) {
            [matrix[i][j], matrix[n - 1 - i][j]] = [matrix[n - 1 - i][j], matrix[i][j]];
        }
    }
    // 主对角线翻转
    for (let i = 0; i < n; i++) {
        // 这里是n * n的矩阵，所以把左下方翻到右上方
        for (let j = 0; j < i; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    return matrix
}


let matrix3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
let matrix4 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate2(matrix3)
console.log(matrix3);

rotate2(matrix4)
console.log(matrix4);